package Offer085;

import java.util.ArrayList;
import java.util.List;

/**
 * 生成匹配的括号
 * 正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * @author 23737
 * @time 2021.11.18
 */
public class Test {
    public static void main(String[] args) {

    }
}

/**
 * dfs回溯
 */
class Solution {
    List<String> ans = new ArrayList<String>();
    StringBuilder sb = new StringBuilder();
    public List<String> generateParenthesis(int n) {
        dfs(0, 0, n);
        return ans;
    }
    public void dfs(int l, int r, int n) { //分别代表当前左括号数、右括号数、题目要求的括号对数
        if (r > l || l > n || r > n) return; //右括号数量多于左括号、左/右括号数量超出，这些情况都是不符合的
        if (l == n && r == n) { //左右括号均达到数量要求
            ans.add(sb.toString()); //添加结果
            return;
        }
        //尝试添加左括号
        sb.append('(');
        dfs(l + 1, r, n);
        sb.deleteCharAt(sb.length() - 1);
        //尝试添加右括号
        sb.append(')');
        dfs(l, r + 1, n);
        sb.deleteCharAt(sb.length() - 1);
    }
}


class  One{
    public static void main(String[] args) {

    }
}

